public class Sort {

    //快速排序
    //时间复杂度    最好情况o(n^logn)  最坏情况O(n^2) 逆序/有序
    //空间复杂度    最好情况o(logn)  最坏情况O(n) 逆序/有序
    //稳定性 不稳定
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        if(start>=end) {
            return;
        }
        int pivot=partitionHoare(array,start,end);
        quick(array,start,pivot-1);
        quick(array, pivot+1, end);
    }

    private static int partitionHoare(int[] array, int left, int right) {
        int tmp=array[left];
        int i=left;
        while (left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            while(left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }

    private static void swap(int[] array, int left, int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }


    //挖坑法
    private static int partitionHole(int[] array, int left, int right) {
        int tmp=array[left];
        while (left<right){
            while(left<right&&array[right]>=tmp){
                //先走右边是为了防止走左边可能会出现遇到的是大的数据把大的数据放到了最前面
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }

    //前后指针法
    private static int partition(int[] array, int left, int right) {
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if(array[cur]<array[left]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return  prev;
    }

    //快排---Hoare法，挖坑法，前后指针法，这3种方式每次划分后的前后顺序可能不一样
}
